package ycl.important.test.sbj;

import org.junit.Test;

import java.util.Random;

/**
 * 积分题
 *
 * @author: YCL
 * @date: 2021-11-09 16:16:28
 */
public class IntegralSbj {


	/**
	 * 我们做了一个活动，根据用户的积分来抽奖，用户的积分都保存在一个数组里面
	 * arr = [20, 34, 160, 2…]，数组下标就是用户的 ID，则这里：
	 * ID 为 0 的用户的积分是 arr[0] 等于 20 分。
	 * ID 为 1 的用户的积分是 arr[1] 等于 34 分。
	 * 请你设计一个抽奖算法，随机抽出一位中奖用户，要求积分越高中奖概率越高。
	 * 返回值是中奖用户的 ID
	 * PS: 1<= arr.length <= 50000 且 1<= arr[i] <= 50000
	 * 代码写出算法，
	 * 并分析其时间复杂度
	 */
	@Test
	public void test() {
		int[] arr = new int[]{
				20, 34, 160, 28799, 48888,
				1173, 3576, 1884, 7990, 13256
		};//用户各自的积分

		int count = 0;//用户积分统计
		for (int i = 0; i < arr.length; i++) {
			int l = count + arr[i];
			System.out.println("id为 " + i + " 的区间: [" + count + ", " + l + ")");//用户所属区间
			count = l;
		}

		Random r = new Random();
		int num = r.nextInt(count);//随机数
		System.out.println("中奖码: " + num);
		int index = 0;
		for (int i : arr) {
			num -= i;
			if (num <= 0)
				break;
			index++;
		}

		System.out.println("中奖用户的id为: " + index);
	}


	@Test
	public void test3() {
		int[] arr = new int[]{
				1, 2, 3, 100, 200,
				100, 100, 99394, 100
		};
		//1. 获取统计总数
		int count = 0;
		for (int i = 0; i < arr.length; i++) {
			int l = count + arr[i];
			System.out.println("第" + i + "个的区间为:(" + count + "," + l + "]");
			count = l;
		}

		//2. 生成这个总数内的随机数
		Random r = new Random();
		int num = r.nextInt(count);
		System.out.println("num = " + num);

		//3. 一个一个减掉区间, 直到这个数字为负数为止
		int index = 0;
		for (int i : arr) {
			num -= i;//num = num - i
			if (num <= 0) {
				break;
			}
			index++;
		}
		System.out.println("中奖下标为: " + index);
	}

	@Test
	public void test2() {
		int[] arr = new int[]{
				1, 2, 3, 100, 200,
				100, 100, 99394, 100
		};

		//1. 统计
		int count = 0;
		for (int i = 0; i < arr.length; i++) {
			int l = count + arr[i];
			System.out.println("第" + i + "个区间为: (" + count + ", " + l + "]");
			count = l;
		}

		//2. 生成随机数
		Random r = new Random();
		int num = r.nextInt(count);
		System.out.println("num = " + num);

		int index = 0;
		for (int i : arr) {
			num -= i;
			if (num <= 0) {
				break;
			}
			index++;
		}

		System.out.println("中奖的下标为:" + index);
	}

	@Test
	public void test1() {
		int[] arr = new int[]{
				1, 2, 3, 100, 200,
				100, 100, 99394, 100
		};

		//1. 统计总数
		int count = 0;
		for (int i = 0; i < arr.length; i++) {
			int l = count + arr[i];
			System.out.println("第" + i + "个区间为: (" + count + "," + l + "]");
			count = l;
		}

		//2. 生成随机数
		Random r = new Random();
		int num = r.nextInt(count);
		System.out.println("num = " + num);

		int index = 0;
		for (int i : arr) {
			num -= i;
			if (num <= 0) {
				break;
			}
			index++;
		}

		System.out.println("中奖的下标为:" + index);
	}
}
